home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / tk2.3 / dist / tkTrig.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-24  |  31.5 KB  |  1,186 lines
  1. /* 
  2.  * tkTrig.c --
  3.  *
  4.  *    This file contains a collection of trigonometry utility
  5.  *    routines that are used by Tk and in particular by the
  6.  *    canvas code.  It also has miscellaneous geometry functions
  7.  *    used by canvases.
  8.  *
  9.  * Copyright 1992 Regents of the University of California.
  10.  * Permission to use, copy, modify, and distribute this
  11.  * software and its documentation for any purpose and without
  12.  * fee is hereby granted, provided that the above copyright
  13.  * notice appear in all copies.  The University of California
  14.  * makes no representations about the suitability of this
  15.  * software for any purpose.  It is provided "as is" without
  16.  * express or implied warranty.
  17.  */
  18.  
  19. #ifndef lint
  20. static char rcsid[] = "$Header: /user6/ouster/wish/RCS/tkTrig.c,v 1.8 92/08/24 09:24:14 ouster Exp $ SPRITE (Berkeley)";
  21. #endif
  22.  
  23. #include <stdio.h>
  24. #include <math.h>
  25. #include "tkConfig.h"
  26. #include "tkCanvas.h"
  27.  
  28. #undef MIN
  29. #define MIN(a,b) (((a) < (b)) ? (a) : (b))
  30. #undef MAX
  31. #define MAX(a,b) (((a) > (b)) ? (a) : (b))
  32. #define PI 3.14159265358979323846
  33.  
  34. /*
  35.  *--------------------------------------------------------------
  36.  *
  37.  * TkLineToPoint --
  38.  *
  39.  *    Compute the distance from a point to a finite line segment.
  40.  *
  41.  * Results:
  42.  *    The return value is the distance from the line segment
  43.  *    whose end-points are *end1Ptr and *end2Ptr to the point
  44.  *    given by *pointPtr.
  45.  *
  46.  * Side effects:
  47.  *    None.
  48.  *
  49.  *--------------------------------------------------------------
  50.  */
  51.  
  52. double
  53. TkLineToPoint(end1Ptr, end2Ptr, pointPtr)
  54.     double end1Ptr[2];        /* Coordinates of first end-point of line. */
  55.     double end2Ptr[2];        /* Coordinates of second end-point of line. */
  56.     double pointPtr[2];        /* Points to coords for point. */
  57. {
  58.     double x, y;
  59.  
  60.     /*
  61.      * Compute the point on the line that is closest to the
  62.      * point.  This must be done separately for vertical edges,
  63.      * horizontal edges, and other edges.
  64.      */
  65.  
  66.     if (end1Ptr[0] == end2Ptr[0]) {
  67.  
  68.     /*
  69.      * Vertical edge.
  70.      */
  71.  
  72.     x = end1Ptr[0];
  73.     if (end1Ptr[1] >= end2Ptr[1]) {
  74.         y = MIN(end1Ptr[1], pointPtr[1]);
  75.         y = MAX(y, end2Ptr[1]);
  76.     } else {
  77.         y = MIN(end2Ptr[1], pointPtr[1]);
  78.         y = MAX(y, end1Ptr[1]);
  79.     }
  80.     } else if (end1Ptr[1] == end2Ptr[1]) {
  81.  
  82.     /*
  83.      * Horizontal edge.
  84.      */
  85.  
  86.     y = end1Ptr[1];
  87.     if (end1Ptr[0] >= end2Ptr[0]) {
  88.         x = MIN(end1Ptr[0], pointPtr[0]);
  89.         x = MAX(x, end2Ptr[0]);
  90.     } else {
  91.         x = MIN(end2Ptr[0], pointPtr[0]);
  92.         x = MAX(x, end1Ptr[0]);
  93.     }
  94.     } else {
  95.     double m1, b1, m2, b2;
  96.  
  97.     /*
  98.      * The edge is neither horizontal nor vertical.  Convert the
  99.      * edge to a line equation of the form y = m1*x + b1.  Then
  100.      * compute a line perpendicular to this edge but passing
  101.      * through the point, also in the form y = m2*x + b2.
  102.      */
  103.  
  104.     m1 = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]);
  105.     b1 = end1Ptr[1] - m1*end1Ptr[0];
  106.     m2 = -1.0/m1;
  107.     b2 = pointPtr[1] - m2*pointPtr[0];
  108.     x = (b2 - b1)/(m1 - m2);
  109.     y = m1*x + b1;
  110.     if (end1Ptr[0] > end2Ptr[0]) {
  111.         if (x > end1Ptr[0]) {
  112.         x = end1Ptr[0];
  113.         y = end1Ptr[1];
  114.         } else if (x < end2Ptr[0]) {
  115.         x = end2Ptr[0];
  116.         y = end2Ptr[1];
  117.         }
  118.     } else {
  119.         if (x > end2Ptr[0]) {
  120.         x = end2Ptr[0];
  121.         y = end2Ptr[1];
  122.         } else if (x < end1Ptr[0]) {
  123.         x = end1Ptr[0];
  124.         y = end1Ptr[1];
  125.         }
  126.     }
  127.     }
  128.  
  129.     /*
  130.      * Compute the distance to the closest point.
  131.      */
  132.  
  133.     return hypot(pointPtr[0] - x, pointPtr[1] - y);
  134. }
  135.  
  136. /*
  137.  *--------------------------------------------------------------
  138.  *
  139.  * TkLineToArea --
  140.  *
  141.  *    Determine whether a line lies entirely inside, entirely
  142.  *    outside, or overlapping a given rectangular area.
  143.  *
  144.  * Results:
  145.  *    -1 is returned if the line given by end1Ptr and end2Ptr
  146.  *    is entirely outside the rectangle given by rectPtr.  0 is
  147.  *    returned if the polygon overlaps the rectangle, and 1 is
  148.  *    returned if the polygon is entirely inside the rectangle.
  149.  *
  150.  * Side effects:
  151.  *    None.
  152.  *
  153.  *--------------------------------------------------------------
  154.  */
  155.  
  156. int
  157. TkLineToArea(end1Ptr, end2Ptr, rectPtr)
  158.     double end1Ptr[2];        /* X and y coordinates for one endpoint
  159.                  * of line. */
  160.     double end2Ptr[2];        /* X and y coordinates for other endpoint
  161.                  * of line. */
  162.     double rectPtr[4];        /* Points to coords for rectangle, in the
  163.                  * order x1, y1, x2, y2.  X1 must be no
  164.                  * larger than x2, and y1 no larger than y2. */
  165. {
  166.     int inside1, inside2;
  167.  
  168.     /*
  169.      * First check the two points individually to see whether they
  170.      * are inside the rectangle or not.
  171.      */
  172.  
  173.     inside1 = (end1Ptr[0] >= rectPtr[0]) && (end1Ptr[0] <= rectPtr[2])
  174.         && (end1Ptr[1] >= rectPtr[1]) && (end1Ptr[1] <= rectPtr[3]);
  175.     inside2 = (end2Ptr[0] >= rectPtr[0]) && (end2Ptr[0] <= rectPtr[2])
  176.         && (end2Ptr[1] >= rectPtr[1]) && (end2Ptr[1] <= rectPtr[3]);
  177.     if (inside1 != inside2) {
  178.     return 0;
  179.     }
  180.     if (inside1 & inside2) {
  181.     return 1;
  182.     }
  183.  
  184.     /*
  185.      * Both points are outside the rectangle, but still need to check
  186.      * for intersections between the line and the rectangle.  Horizontal
  187.      * and vertical lines are particularly easy, so handle them
  188.      * separately.
  189.      */
  190.  
  191.     if (end1Ptr[0] == end2Ptr[0]) {
  192.     /*
  193.      * Vertical line.
  194.      */
  195.     
  196.     if (((end1Ptr[1] >= rectPtr[1]) ^ (end2Ptr[1] >= rectPtr[1]))
  197.         && (end1Ptr[0] >= rectPtr[0])
  198.         && (end1Ptr[0] <= rectPtr[2])) {
  199.         return 0;
  200.     }
  201.     } else if (end1Ptr[1] == end2Ptr[1]) {
  202.     /*
  203.      * Horizontal line.
  204.      */
  205.     
  206.     if (((end1Ptr[0] >= rectPtr[0]) ^ (end2Ptr[0] >= rectPtr[0]))
  207.         && (end1Ptr[1] >= rectPtr[1])
  208.         && (end1Ptr[1] <= rectPtr[3])) {
  209.         return 0;
  210.     }
  211.     } else {
  212.     double m, x, y, low, high;
  213.     
  214.     /*
  215.      * Diagonal line.  Compute slope of line and use
  216.      * for intersection checks against each of the
  217.      * sides of the rectangle: left, right, bottom, top.
  218.      */
  219.     
  220.     m = (end2Ptr[1] - end1Ptr[1])/(end2Ptr[0] - end1Ptr[0]);
  221.     if (end1Ptr[0] < end2Ptr[0]) {
  222.         low = end1Ptr[0];  high = end2Ptr[0];
  223.     } else {
  224.         low = end2Ptr[0]; high = end1Ptr[0];
  225.     }
  226.     
  227.     /*
  228.      * Left edge.
  229.      */
  230.     
  231.     y = end1Ptr[1] + (rectPtr[0] - end1Ptr[0])*m;
  232.     if ((rectPtr[0] >= low) && (rectPtr[0] <= high)
  233.         && (y >= rectPtr[1]) && (y <= rectPtr[3])) {
  234.         return 0;
  235.     }
  236.     
  237.     /*
  238.      * Right edge.
  239.      */
  240.     
  241.     y += (rectPtr[2] - rectPtr[0])*m;
  242.     if ((y >= rectPtr[1]) && (y <= rectPtr[3])
  243.         && (rectPtr[2] >= low) && (rectPtr[2] <= high)) {
  244.         return 0;
  245.     }
  246.     
  247.     /*
  248.      * Bottom edge.
  249.      */
  250.     
  251.     if (end1Ptr[1] < end2Ptr[1]) {
  252.         low = end1Ptr[1];  high = end2Ptr[1];
  253.     } else {
  254.         low = end2Ptr[1]; high = end1Ptr[1];
  255.     }
  256.     x = end1Ptr[0] + (rectPtr[1] - end1Ptr[1])/m;
  257.     if ((x >= rectPtr[0]) && (x <= rectPtr[2])
  258.         && (rectPtr[1] >= low) && (rectPtr[1] <= high)) {
  259.         return 0;
  260.     }
  261.     
  262.     /*
  263.      * Top edge.
  264.      */
  265.     
  266.     x += (rectPtr[3] - rectPtr[1])/m;
  267.     if ((x >= rectPtr[0]) && (x <= rectPtr[2])
  268.         && (rectPtr[3] >= low) && (rectPtr[3] <= high)) {
  269.         return 0;
  270.     }
  271.     }
  272.     return -1;
  273. }
  274.  
  275. /*
  276.  *--------------------------------------------------------------
  277.  *
  278.  * TkPolygonToPoint --
  279.  *
  280.  *    Compute the distance from a point to a polygon.
  281.  *
  282.  * Results:
  283.  *    The return value is 0.0 if the point referred to by
  284.  *    pointPtr is within the polygon referred to by polyPtr
  285.  *    and numPoints.  Otherwise the return value is the
  286.  *    distance of the point from the polygon.
  287.  *
  288.  * Side effects:
  289.  *    None.
  290.  *
  291.  *--------------------------------------------------------------
  292.  */
  293.  
  294. double
  295. TkPolygonToPoint(polyPtr, numPoints, pointPtr)
  296.     double *polyPtr;        /* Points to an array coordinates for
  297.                  * closed polygon:  x0, y0, x1, y1, ...
  298.                  * The polygon may be self-intersecting. */
  299.     int numPoints;        /* Total number of points at *polyPtr. */
  300.     double *pointPtr;        /* Points to coords for point. */
  301. {
  302.     double bestDist;        /* Closest distance between point and
  303.                  * any edge in polygon. */
  304.     int intersections;        /* Number of edges in the polygon that
  305.                  * intersect a ray extending vertically
  306.                  * upwards from the point to infinity. */
  307.     int count;
  308.     register double *pPtr;
  309.  
  310.     /*
  311.      * Iterate through all of the edges in the polygon, updating
  312.      * bestDist and intersections.
  313.      *
  314.      * TRICKY POINT:  when computing intersections, include left
  315.      * x-coordinate of line within its range, but not y-coordinate.
  316.      * Otherwise if the point lies exactly below a vertex we'll
  317.      * count it as two intersections.
  318.      */
  319.  
  320.     bestDist = 1.0e40;
  321.     intersections = 0;
  322.  
  323.     for (count = numPoints, pPtr = polyPtr; count > 1; count--, pPtr += 2) {
  324.     double x, y, dist;
  325.  
  326.     /*
  327.      * Compute the point on the current edge closest to the point
  328.      * and update the intersection count.  This must be done
  329.      * separately for vertical edges, horizontal edges, and
  330.      * other edges.
  331.      */
  332.  
  333.     if (pPtr[2] == pPtr[0]) {
  334.  
  335.         /*
  336.          * Vertical edge.
  337.          */
  338.  
  339.         x = pPtr[0];
  340.         if (pPtr[1] >= pPtr[3]) {
  341.         y = MIN(pPtr[1], pointPtr[1]);
  342.         y = MAX(y, pPtr[3]);
  343.         } else {
  344.         y = MIN(pPtr[3], pointPtr[1]);
  345.         y = MAX(y, pPtr[1]);
  346.         }
  347.     } else if (pPtr[3] == pPtr[1]) {
  348.  
  349.         /*
  350.          * Horizontal edge.
  351.          */
  352.  
  353.         y = pPtr[1];
  354.         if (pPtr[0] >= pPtr[2]) {
  355.         x = MIN(pPtr[0], pointPtr[0]);
  356.         x = MAX(x, pPtr[2]);
  357.         if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[0])
  358.             && (pointPtr[0] >= pPtr[2])) {
  359.             intersections++;
  360.         }
  361.         } else {
  362.         x = MIN(pPtr[2], pointPtr[0]);
  363.         x = MAX(x, pPtr[0]);
  364.         if ((pointPtr[1] < y) && (pointPtr[0] < pPtr[2])
  365.             && (pointPtr[0] >= pPtr[0])) {
  366.             intersections++;
  367.         }
  368.         }
  369.     } else {
  370.         double m1, b1, m2, b2;
  371.         int lower;            /* Non-zero means point below line. */
  372.  
  373.         /*
  374.          * The edge is neither horizontal nor vertical.  Convert the
  375.          * edge to a line equation of the form y = m1*x + b1.  Then
  376.          * compute a line perpendicular to this edge but passing
  377.          * through the point, also in the form y = m2*x + b2.
  378.          */
  379.  
  380.         m1 = (pPtr[3] - pPtr[1])/(pPtr[2] - pPtr[0]);
  381.         b1 = pPtr[1] - m1*pPtr[0];
  382.         m2 = -1.0/m1;
  383.         b2 = pointPtr[1] - m2*pointPtr[0];
  384.         x = (b2 - b1)/(m1 - m2);
  385.         y = m1*x + b1;
  386.         if (pPtr[0] > pPtr[2]) {
  387.         if (x > pPtr[0]) {
  388.             x = pPtr[0];
  389.             y = pPtr[1];
  390.         } else if (x < pPtr[2]) {
  391.             x = pPtr[2];
  392.             y = pPtr[3];
  393.         }
  394.         } else {
  395.         if (x > pPtr[2]) {
  396.             x = pPtr[2];
  397.             y = pPtr[3];
  398.         } else if (x < pPtr[0]) {
  399.             x = pPtr[0];
  400.             y = pPtr[1];
  401.         }
  402.         }
  403.         lower = (m1*pointPtr[0] + b1) > pointPtr[1];
  404.         if (lower && (pointPtr[0] >= MIN(pPtr[0], pPtr[2]))
  405.             && (pointPtr[0] < MAX(pPtr[0], pPtr[2]))) {
  406.         intersections++;
  407.         }
  408.     }
  409.  
  410.     /*
  411.      * Compute the distance to the closest point, and see if that
  412.      * is the best distance seen so far.
  413.      */
  414.  
  415.     dist = hypot(pointPtr[0] - x, pointPtr[1] - y);
  416.     if (dist < bestDist) {
  417.         bestDist = dist;
  418.     }
  419.     }
  420.  
  421.     /*
  422.      * We've processed all of the points.  If the number of intersections
  423.      * is odd, the point is inside the polygon.
  424.      */
  425.  
  426.     if (intersections & 0x1) {
  427.     return 0.0;
  428.     }
  429.     return bestDist;
  430. }
  431.  
  432. /*
  433.  *--------------------------------------------------------------
  434.  *
  435.  * TkPolygonToArea --
  436.  *
  437.  *    Determine whether a polygon lies entirely inside, entirely
  438.  *    outside, or overlapping a given rectangular area.
  439.  *
  440.  * Results:
  441.  *    -1 is returned if the polygon given by polyPtr and numPoints
  442.  *    is entirely outside the rectangle given by rectPtr.  0 is
  443.  *    returned if the polygon overlaps the rectangle, and 1 is
  444.  *    returned if the polygon is entirely inside the rectangle.
  445.  *
  446.  * Side effects:
  447.  *    None.
  448.  *
  449.  *--------------------------------------------------------------
  450.  */
  451.  
  452. int
  453. TkPolygonToArea(polyPtr, numPoints, rectPtr)
  454.     double *polyPtr;        /* Points to an array coordinates for
  455.                  * closed polygon:  x0, y0, x1, y1, ...
  456.                  * The polygon may be self-intersecting. */
  457.     int numPoints;        /* Total number of points at *polyPtr. */
  458.     register double *rectPtr;    /* Points to coords for rectangle, in the
  459.                  * order x1, y1, x2, y2.  X1 and y1 must
  460.                  * be lower-left corner. */
  461. {
  462.     int state;            /* State of all edges seen so far (-1 means
  463.                  * outside, 1 means inside, won't ever be
  464.                  * 0). */
  465.     int count;
  466.     register double *pPtr;
  467.  
  468.     /*
  469.      * Iterate over all of the edges of the polygon and test them
  470.      * against the rectangle.  Can quit as soon as the state becomes
  471.      * "intersecting".
  472.      */
  473.  
  474.     state = TkLineToArea(polyPtr, polyPtr+2, rectPtr);
  475.     if (state == 0) {
  476.     return 0;
  477.     }
  478.     for (pPtr = polyPtr+2, count = numPoints-1; count >= 2;
  479.         pPtr += 2, count--) {
  480.     if (TkLineToArea(pPtr, pPtr+2, rectPtr) != state) {
  481.         return 0;
  482.     }
  483.     }
  484.  
  485.     /*
  486.      * If all of the edges were inside the rectangle we're done.
  487.      * If all of the edges were outside, then the rectangle could
  488.      * still intersect the polygon (if it's entirely enclosed).
  489.      * Call TkPolygonToPoint to figure this out.
  490.      */
  491.  
  492.     if (state == 1) {
  493.     return 1;
  494.     }
  495.     if (TkPolygonToPoint(polyPtr, numPoints, rectPtr) == 0.0) {
  496.     return 0;
  497.     }
  498.     return -1;
  499. }
  500.  
  501. /*
  502.  *--------------------------------------------------------------
  503.  *
  504.  * TkOvalToPoint --
  505.  *
  506.  *    Computes the distance from a given point to a given
  507.  *    oval, in canvas units.
  508.  *
  509.  * Results:
  510.  *    The return value is 0 if the point given by *pointPtr is
  511.  *    inside the oval.  If the point isn't inside the
  512.  *    oval then the return value is approximately the distance
  513.  *    from the point to the oval.  If the oval is filled, then
  514.  *    anywhere in the interior is considered "inside";  if
  515.  *    the oval isn't filled, then "inside" means only the area
  516.  *    occupied by the outline.
  517.  *
  518.  * Side effects:
  519.  *    None.
  520.  *
  521.  *--------------------------------------------------------------
  522.  */
  523.  
  524.     /* ARGSUSED */
  525. double
  526. TkOvalToPoint(ovalPtr, width, filled, pointPtr)
  527.     double ovalPtr[4];        /* Pointer to array of four coordinates
  528.                  * (x1, y1, x2, y2) defining oval's bounding
  529.                  * box. */
  530.     double width;        /* Width of outline for oval. */
  531.     int filled;            /* Non-zero means oval should be treated as
  532.                  * filled;  zero means only consider outline. */
  533.     double pointPtr[2];        /* Coordinates of point. */
  534. {
  535.     double xDelta, yDelta, scaledDistance, distToOutline, distToCenter;
  536.  
  537.     /*
  538.      * Compute the distance between the center of the oval and the
  539.      * point in question, using a coordinate system where the oval
  540.      * has been transformed to a circle with unit radius.
  541.      */
  542.  
  543.     xDelta = (pointPtr[0] - (ovalPtr[0] + ovalPtr[2])/2.0);
  544.     yDelta = (pointPtr[1] - (ovalPtr[1] + ovalPtr[3])/2.0);
  545.     distToCenter = hypot(xDelta, yDelta);
  546.     scaledDistance = hypot(xDelta / ((ovalPtr[2] + width - ovalPtr[0])/2.0),
  547.         yDelta / ((ovalPtr[3] + width - ovalPtr[1])/2.0));
  548.  
  549.  
  550.     /*
  551.      * If the scaled distance is greater than 1 then it means no
  552.      * hit.  Compute the distance from the point to the edge of
  553.      * the circle, then scale this distance back to the original
  554.      * coordinate system.
  555.      *
  556.      * Note: this distance isn't completely accurate.  It's only
  557.      * an approximation, and it can overestimate the correct
  558.      * distance when the oval is eccentric.
  559.      */
  560.  
  561.     if (scaledDistance > 1.0) {
  562.     return (distToCenter/scaledDistance) * (scaledDistance - 1.0);
  563.     }
  564.  
  565.     /*
  566.      * Scaled distance less than 1 means the point is inside the
  567.      * outer edge of the oval.  If this is a filled oval, then we
  568.      * have a hit.  Otherwise, do the same computation as above
  569.      * (scale back to original coordinate system), but also check
  570.      * to see if the point is within the width of the outline.
  571.      */
  572.  
  573.     if (filled) {
  574.     return 0.0;
  575.     }
  576.     distToOutline = (distToCenter/scaledDistance) * (1.0 - scaledDistance)
  577.         - width;
  578.     if (distToOutline < 0.0) {
  579.     return 0.0;
  580.     }
  581.     return distToOutline;
  582. }
  583.  
  584. /*
  585.  *--------------------------------------------------------------
  586.  *
  587.  * TkOvalToArea --
  588.  *
  589.  *    Determine whether an oval lies entirely inside, entirely
  590.  *    outside, or overlapping a given rectangular area.
  591.  *
  592.  * Results:
  593.  *    -1 is returned if the oval described by ovalPtr is entirely
  594.  *    outside the rectangle given by rectPtr.  0 is returned if the
  595.  *    oval overlaps the rectangle, and 1 is returned if the oval
  596.  *    is entirely inside the rectangle.
  597.  *
  598.  * Side effects:
  599.  *    None.
  600.  *
  601.  *--------------------------------------------------------------
  602.  */
  603.  
  604. int
  605. TkOvalToArea(ovalPtr, rectPtr)
  606.     register double *ovalPtr;    /* Points to coordinates definining the
  607.                  * bounding rectangle for the oval: x1, y1,
  608.                  * x2, y2.  X1 must be less than x2 and y1
  609.                  * less than y2. */
  610.     register double *rectPtr;    /* Points to coords for rectangle, in the
  611.                  * order x1, y1, x2, y2.  X1 and y1 must
  612.                  * be lower-left corner. */
  613. {
  614.     double centerX, centerY, radX, radY, deltaX, deltaY;
  615.  
  616.     /*
  617.      * First, see if oval is entirely inside rectangle or entirely
  618.      * outside rectangle.
  619.      */
  620.  
  621.     if ((rectPtr[0] <= ovalPtr[0]) && (rectPtr[2] >= ovalPtr[2])
  622.         && (rectPtr[1] <= ovalPtr[1]) && (rectPtr[3] >= ovalPtr[3])) {
  623.     return 1;
  624.     }
  625.     if ((rectPtr[2] < ovalPtr[0]) || (rectPtr[0] > ovalPtr[2])
  626.         || (rectPtr[3] < ovalPtr[1]) || (rectPtr[1] > ovalPtr[3])) {
  627.     return -1;
  628.     }
  629.  
  630.     /*
  631.      * Next, go through the rectangle side by side.  For each side
  632.      * of the rectangle, find the point on the side that is closest
  633.      * to the oval's center, and see if that point is inside the
  634.      * oval.  If at least one such point is inside the oval, then
  635.      * the rectangle intersects the oval.
  636.      */
  637.  
  638.     centerX = (ovalPtr[0] + ovalPtr[2])/2;
  639.     centerY = (ovalPtr[1] + ovalPtr[3])/2;
  640.     radX = (ovalPtr[2] - ovalPtr[0])/2;
  641.     radY = (ovalPtr[3] - ovalPtr[1])/2;
  642.  
  643.     deltaY = rectPtr[1] - centerY;
  644.     if (deltaY < 0.0) {
  645.     deltaY = centerY - rectPtr[3];
  646.     if (deltaY < 0.0) {
  647.         deltaY = 0;
  648.     }
  649.     }
  650.     deltaY /= radY;
  651.     deltaY *= deltaY;
  652.  
  653.     /*
  654.      * Left side:
  655.      */
  656.  
  657.     deltaX = (rectPtr[0] - centerX)/radX;
  658.     deltaX *= deltaX;
  659.     if ((deltaX + deltaY) <= 1.0) {
  660.     return 0;
  661.     }
  662.  
  663.     /*
  664.      * Right side:
  665.      */
  666.  
  667.     deltaX = (rectPtr[2] - centerX)/radX;
  668.     deltaX *= deltaX;
  669.     if ((deltaX + deltaY) <= 1.0) {
  670.     return 0;
  671.     }
  672.  
  673.     deltaX = rectPtr[0] - centerX;
  674.     if (deltaX < 0.0) {
  675.     deltaX = centerX - rectPtr[2];
  676.     if (deltaX < 0.0) {
  677.         deltaX = 0;
  678.     }
  679.     }
  680.     deltaX /= radX;
  681.     deltaX *= deltaX;
  682.  
  683.     /*
  684.      * Bottom side:
  685.      */
  686.  
  687.     deltaY = (rectPtr[1] - centerY)/radY;
  688.     deltaY *= deltaY;
  689.     if ((deltaX + deltaY) < 1.0) {
  690.     return 0;
  691.     }
  692.  
  693.     /*
  694.      * Top side:
  695.      */
  696.  
  697.     deltaY = (rectPtr[3] - centerY)/radY;
  698.     deltaY *= deltaY;
  699.     if ((deltaX + deltaY) < 1.0) {
  700.     return 0;
  701.     }
  702.  
  703.     return -1;
  704. }
  705.  
  706. /*
  707.  *--------------------------------------------------------------
  708.  *
  709.  * TkIncludePoint --
  710.  *
  711.  *    Given a point and a generic canvas item header, expand
  712.  *    the item's bounding box if needed to include the point.
  713.  *
  714.  * Results:
  715.  *    None.
  716.  *
  717.  * Side effects:
  718.  *    The boudn.
  719.  *
  720.  *--------------------------------------------------------------
  721.  */
  722.  
  723.     /* ARGSUSED */
  724. void
  725. TkIncludePoint(canvasPtr, itemPtr, pointPtr)
  726.     Tk_Canvas *canvasPtr;        /* Canvas containing item. */
  727.     register Tk_Item *itemPtr;        /* Item whose bounding box is
  728.                      * being calculated. */
  729.     double *pointPtr;            /* Address of two doubles giving
  730.                      * x and y coordinates of point. */
  731. {
  732.     int tmp;
  733.  
  734.     tmp = pointPtr[0] + 0.5;
  735.     if (tmp < itemPtr->x1) {
  736.     itemPtr->x1 = tmp;
  737.     }
  738.     if (tmp > itemPtr->x2) {
  739.     itemPtr->x2 = tmp;
  740.     }
  741.     tmp = pointPtr[1] + 0.5;
  742.     if (tmp < itemPtr->y1) {
  743.     itemPtr->y1 = tmp;
  744.     }
  745.     if (tmp > itemPtr->y2) {
  746.     itemPtr->y2 = tmp;
  747.     }
  748. }
  749.  
  750. /*
  751.  *--------------------------------------------------------------
  752.  *
  753.  * TkBezierScreenPoints --
  754.  *
  755.  *    Given four control points, create a larger set of XPoints
  756.  *    for a Bezier spline based on the points.
  757.  *
  758.  * Results:
  759.  *    The array at *xPointPtr gets filled in with numSteps XPoints
  760.  *    corresponding to the Bezier spline defined by the four 
  761.  *    control points.  Note:  no output point is generated for the
  762.  *    first input point, but an output point *is* generated for
  763.  *    the last input point.
  764.  *
  765.  * Side effects:
  766.  *    None.
  767.  *
  768.  *--------------------------------------------------------------
  769.  */
  770.  
  771. void
  772. TkBezierScreenPoints(canvasPtr, control, numSteps, xPointPtr)
  773.     Tk_Canvas *canvasPtr;        /* Canvas in which curve is to be
  774.                      * drawn. */
  775.     double control[];            /* Array of coordinates for four
  776.                      * control points:  x0, y0, x1, y1,
  777.                      * ... x3 y3. */
  778.     int numSteps;            /* Number of curve points to
  779.                      * generate.  */
  780.     register XPoint *xPointPtr;        /* Where to put new points. */
  781. {
  782.     int i;
  783.     double u, u2, u3, t, t2, t3;
  784.  
  785.     for (i = 1; i <= numSteps; i++, xPointPtr++) {
  786.     t = ((double) i)/((double) numSteps);
  787.     t2 = t*t;
  788.     t3 = t2*t;
  789.     u = 1.0 - t;
  790.     u2 = u*u;
  791.     u3 = u2*u;
  792.     xPointPtr->x = SCREEN_X(canvasPtr, (control[0]*u3
  793.         + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3));
  794.     xPointPtr->y = SCREEN_Y(canvasPtr, (control[1]*u3
  795.         + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3));
  796.     }
  797. }
  798.  
  799. /*
  800.  *--------------------------------------------------------------
  801.  *
  802.  * TkBezierPoints --
  803.  *
  804.  *    Given four control points, create a larger set of points
  805.  *    for a Bezier spline based on the points.
  806.  *
  807.  * Results:
  808.  *    The array at *coordPtr gets filled in with 2*numSteps
  809.  *    coordinates, which correspond to the Bezier spline defined
  810.  *    by the four control points.  Note:  no output point is
  811.  *    generated for the first input point, but an output point
  812.  *    *is* generated for the last input point.
  813.  *
  814.  * Side effects:
  815.  *    None.
  816.  *
  817.  *--------------------------------------------------------------
  818.  */
  819.  
  820. void
  821. TkBezierPoints(control, numSteps, coordPtr)
  822.     double control[];            /* Array of coordinates for four
  823.                      * control points:  x0, y0, x1, y1,
  824.                      * ... x3 y3. */
  825.     int numSteps;            /* Number of curve points to
  826.                      * generate.  */
  827.     register double *coordPtr;        /* Where to put new points. */
  828. {
  829.     int i;
  830.     double u, u2, u3, t, t2, t3;
  831.  
  832.     for (i = 1; i <= numSteps; i++, coordPtr += 2) {
  833.     t = ((double) i)/((double) numSteps);
  834.     t2 = t*t;
  835.     t3 = t2*t;
  836.     u = 1.0 - t;
  837.     u2 = u*u;
  838.     u3 = u2*u;
  839.     coordPtr[0] = control[0]*u3
  840.         + 3.0 * (control[2]*t*u2 + control[4]*t2*u) + control[6]*t3;
  841.     coordPtr[1] = control[1]*u3
  842.         + 3.0 * (control[3]*t*u2 + control[5]*t2*u) + control[7]*t3;
  843.     }
  844. }
  845.  
  846. /*
  847.  *--------------------------------------------------------------
  848.  *
  849.  * TkMakeBezierCurve --
  850.  *
  851.  *    Given a set of points, create a new set of points that
  852.  *    fit Bezier splines to the line segments connecting the
  853.  *    original points.  Produces output points in either of two
  854.  *    forms.
  855.  *
  856.  * Results:
  857.  *    Either or both of the xPoints or dblPoints arrays are filled
  858.  *    in.  The return value is the number of points placed in the
  859.  *    arrays.  Note:  if the first and last points are the same, then
  860.  *    a closed curve is generated.
  861.  *
  862.  * Side effects:
  863.  *    None.
  864.  *
  865.  *--------------------------------------------------------------
  866.  */
  867.  
  868. int
  869. TkMakeBezierCurve(canvasPtr, pointPtr, numPoints, numSteps, xPoints, dblPoints)
  870.     Tk_Canvas *canvasPtr;        /* Canvas in which curve is to be
  871.                      * drawn. */
  872.     double *pointPtr;            /* Array of input coordinates:  x0,
  873.                      * y0, x1, y1, etc.. */
  874.     int numPoints;            /* Number of points at pointPtr. */
  875.     int numSteps;            /* Number of steps to use for each
  876.                      * spline segments (determines
  877.                      * smoothness of curve). */
  878.     XPoint xPoints[];            /* Array of XPoints to fill in (e.g.
  879.                      * for display.  NULL means don't
  880.                      * fill in any XPoints. */
  881.     double dblPoints[];            /* Array of points to fill in as
  882.                      * doubles, in the form x0, y0,
  883.                      * x1, y1, ....  NULL means don't
  884.                      * fill in anything in this form. 
  885.                      * Caller must make sure that this
  886.                      * array has enough space. */
  887. {
  888.     int closed, outputPoints, i;
  889.     int numCoords = numPoints*2;
  890.     double control[8];
  891.  
  892.     /*
  893.      * If the curve is a closed one then generate a special spline
  894.      * that spans the last points and the first ones.  Otherwise
  895.      * just put the first point into the output.
  896.      */
  897.  
  898.     outputPoints = 0;
  899.     if ((pointPtr[0] == pointPtr[numCoords-2])
  900.         && (pointPtr[1] == pointPtr[numCoords-1])) {
  901.     closed = 1;
  902.     control[0] = 0.5*pointPtr[numCoords-4] + 0.5*pointPtr[0];
  903.     control[1] = 0.5*pointPtr[numCoords-3] + 0.5*pointPtr[1];
  904.     control[2] = 0.167*pointPtr[numCoords-4] + 0.833*pointPtr[0];
  905.     control[3] = 0.167*pointPtr[numCoords-3] + 0.833*pointPtr[1];
  906.     control[4] = 0.833*pointPtr[0] + 0.167*pointPtr[2];
  907.     control[5] = 0.833*pointPtr[1] + 0.167*pointPtr[3];
  908.     control[6] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
  909.     control[7] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
  910.     if (xPoints != NULL) {
  911.         xPoints->x = SCREEN_X(canvasPtr, control[0]);
  912.         xPoints->y = SCREEN_Y(canvasPtr, control[1]);
  913.         TkBezierScreenPoints(canvasPtr, control, numSteps, xPoints+1);
  914.         xPoints += numSteps+1;
  915.     }
  916.     if (dblPoints != NULL) {
  917.         dblPoints[0] = control[0];
  918.         dblPoints[1] = control[1];
  919.         TkBezierPoints(control, numSteps, dblPoints+2);
  920.         dblPoints += 2*(numSteps+1);
  921.     }
  922.     outputPoints += numSteps+1;
  923.     } else {
  924.     closed = 0;
  925.     if (xPoints != NULL) {
  926.         xPoints->x = SCREEN_X(canvasPtr, pointPtr[0]);
  927.         xPoints->y = SCREEN_Y(canvasPtr, pointPtr[1]);
  928.         xPoints += 1;
  929.     }
  930.     if (dblPoints != NULL) {
  931.         dblPoints[0] = pointPtr[0];
  932.         dblPoints[1] = pointPtr[1];
  933.         dblPoints += 2;
  934.     }
  935.     outputPoints += 1;
  936.     }
  937.  
  938.     for (i = 2; i < numPoints; i++, pointPtr += 2) {
  939.     /*
  940.      * Set up the first two control points.  This is done
  941.      * differently for the first spline of an open curve
  942.      * than for other cases.
  943.      */
  944.  
  945.     if ((i == 2) && !closed) {
  946.         control[0] = pointPtr[0];
  947.         control[1] = pointPtr[1];
  948.         control[2] = 0.333*pointPtr[0] + 0.667*pointPtr[2];
  949.         control[3] = 0.333*pointPtr[1] + 0.667*pointPtr[3];
  950.     } else {
  951.         control[0] = 0.5*pointPtr[0] + 0.5*pointPtr[2];
  952.         control[1] = 0.5*pointPtr[1] + 0.5*pointPtr[3];
  953.         control[2] = 0.167*pointPtr[0] + 0.833*pointPtr[2];
  954.         control[3] = 0.167*pointPtr[1] + 0.833*pointPtr[3];
  955.     }
  956.  
  957.     /*
  958.      * Set up the last two control points.  This is done
  959.      * differently for the last spline of an open curve
  960.      * than for other cases.
  961.      */
  962.  
  963.     if ((i == (numPoints-1)) && !closed) {
  964.         control[4] = .667*pointPtr[2] + .333*pointPtr[4];
  965.         control[5] = .667*pointPtr[3] + .333*pointPtr[5];
  966.         control[6] = pointPtr[4];
  967.         control[7] = pointPtr[5];
  968.     } else {
  969.         control[4] = .833*pointPtr[2] + .167*pointPtr[4];
  970.         control[5] = .833*pointPtr[3] + .167*pointPtr[5];
  971.         control[6] = 0.5*pointPtr[2] + 0.5*pointPtr[4];
  972.         control[7] = 0.5*pointPtr[3] + 0.5*pointPtr[5];
  973.     }
  974.  
  975.     /*
  976.      * If the first two points coincide, or if the last
  977.      * two points coincide, then generate a single
  978.      * straight-line segment by outputting the last control
  979.      * point.
  980.      */
  981.  
  982.     if (((pointPtr[0] == pointPtr[2]) && (pointPtr[1] == pointPtr[3]))
  983.         || ((pointPtr[2] == pointPtr[4])
  984.         && (pointPtr[3] == pointPtr[5]))) {
  985.         if (xPoints != NULL) {
  986.         xPoints[0].x = SCREEN_X(canvasPtr, control[6]);
  987.         xPoints[0].y = SCREEN_Y(canvasPtr, control[7]);
  988.         xPoints++;
  989.         }
  990.         if (dblPoints != NULL) {
  991.         dblPoints[0] = control[6];
  992.         dblPoints[1] = control[7];
  993.         dblPoints += 2;
  994.         }
  995.         outputPoints += 1;
  996.         continue;
  997.     }
  998.  
  999.     /*
  1000.      * Generate a Bezier spline using the control points.
  1001.      */
  1002.  
  1003.  
  1004.     if (xPoints != NULL) {
  1005.         TkBezierScreenPoints(canvasPtr, control, numSteps, xPoints);
  1006.         xPoints += numSteps;
  1007.     }
  1008.     if (dblPoints != NULL) {
  1009.         TkBezierPoints(control, numSteps, dblPoints);
  1010.         dblPoints += 2*numSteps;
  1011.     }
  1012.     outputPoints += numSteps;
  1013.     }
  1014.     return outputPoints;
  1015. }
  1016.  
  1017. /*
  1018.  *--------------------------------------------------------------
  1019.  *
  1020.  * TkGetMiterPoints --
  1021.  *
  1022.  *    Given three points forming an angle, compute the
  1023.  *    coordinates of the inside and outside points of
  1024.  *    the mitered corner formed by a line of a given
  1025.  *    width at that angle.
  1026.  *
  1027.  * Results:
  1028.  *    If the angle formed by the three points is less than
  1029.  *    11 degrees then 0 is returned and m1 and m2 aren't
  1030.  *    modified.  Otherwise 1 is returned and the points at
  1031.  *    m1 and m2 are filled in with the positions of the points
  1032.  *    of the mitered corner.
  1033.  *
  1034.  * Side effects:
  1035.  *    None.
  1036.  *
  1037.  *--------------------------------------------------------------
  1038.  */
  1039.  
  1040. int
  1041. TkGetMiterPoints(p1, p2, p3, width, m1, m2)
  1042.     double p1[];        /* Points to x- and y-coordinates of point
  1043.                  * before vertex. */
  1044.     double p2[];        /* Points to x- and y-coordinates of vertex
  1045.                  * for mitered joint. */
  1046.     double p3[];        /* Points to x- and y-coordinates of point
  1047.                  * after vertex. */
  1048.     double width;        /* Width of line.  */
  1049.     double m1[];        /* Points to place to put "left" vertex
  1050.                  * point (see as you face from p1 to p2). */
  1051.     double m2[];        /* Points to place to put "right" vertex
  1052.                  * point. */
  1053. {
  1054.     double theta1;        /* Angle of segment p2-p1. */
  1055.     double theta2;        /* Angle of segment p2-p3. */
  1056.     double theta;        /* Angle between line segments (angle
  1057.                  * of joint). */
  1058.     double theta3;        /* Angle that bisects theta1 and
  1059.                  * theta2 and points to m1. */
  1060.     double dist;        /* Distance of miter points from p2. */
  1061.     double deltaX, deltaY;    /* X and y offsets cooresponding to
  1062.                  * dist (fudge factors for bounding
  1063.                  * box). */
  1064.     static float elevenDegrees = (11.0*2.0*PI)/360.0;
  1065.  
  1066.     if (p2[1] == p1[1]) {
  1067.     theta1 = (p2[0] < p1[0]) ? 0 : PI;
  1068.     } else if (p2[0] == p1[0]) {
  1069.     theta1 = (p2[1] < p1[1]) ? PI/2.0 : -PI/2.0;
  1070.     } else {
  1071.     theta1 = atan2(p1[1] - p2[1], p1[0] - p2[0]);
  1072.     }
  1073.     if (p3[1] == p2[1]) {
  1074.     theta2 = (p3[0] > p2[0]) ? 0 : PI;
  1075.     } else if (p3[0] == p2[0]) {
  1076.     theta2 = (p3[1] > p2[1]) ? PI/2.0 : -PI/2.0;
  1077.     } else {
  1078.     theta2 = atan2(p3[1] - p2[1], p3[0] - p2[0]);
  1079.     }
  1080.     theta = theta1 - theta2;
  1081.     if (theta > PI) {
  1082.     theta -= 2*PI;
  1083.     } else if (theta < -PI) {
  1084.     theta += 2*PI;
  1085.     }
  1086.     if ((theta < elevenDegrees) && (theta > -elevenDegrees)) {
  1087.     return 0;
  1088.     }
  1089.     dist = 0.5*width/sin(0.5*theta);
  1090.     if (dist < 0.0) {
  1091.     dist = -dist;
  1092.     }
  1093.  
  1094.     /*
  1095.      * Compute theta3 (make sure that it points to the left when
  1096.      * looking from p1 to p2).
  1097.      */
  1098.  
  1099.     theta3 = (theta1 + theta2)/2.0;
  1100.     if (sin(theta3 - (theta1 + PI)) < 0.0) {
  1101.     theta3 += PI;
  1102.     }
  1103.     deltaX = dist*cos(theta3);
  1104.     m1[0] = p2[0] + deltaX;
  1105.     m2[0] = p2[0] - deltaX;
  1106.     deltaY = dist*sin(theta3);
  1107.     m1[1] = p2[1] + deltaY;
  1108.     m2[1] = p2[1] - deltaY;
  1109.     return 1;
  1110. }
  1111.  
  1112. /*
  1113.  *--------------------------------------------------------------
  1114.  *
  1115.  * TkGetButtPoints --
  1116.  *
  1117.  *    Given two points forming a line segment, compute the
  1118.  *    coordinates of two endpoints of a rectangle formed by
  1119.  *    bloating the line segment until it is width units wide.
  1120.  *
  1121.  * Results:
  1122.  *    There is no return value.  M1 and m2 are filled in to
  1123.  *    correspond to m1 and m2 in the diagram below:
  1124.  *
  1125.  *           ----------------* m1
  1126.  *                   |
  1127.  *        p1 *---------------* p2
  1128.  *                   |
  1129.  *           ----------------* m2
  1130.  *
  1131.  *    M1 and m2 will be W units apart, with p2 centered between
  1132.  *    them and m1-m2 perpendicular to p1-p2.  However, if
  1133.  *    "project" is true then m1 and m2 will be as follows:
  1134.  *
  1135.  *           -------------------* m1
  1136.  *                  p2  |
  1137.  *        p1 *---------------*  |
  1138.  *                      |
  1139.  *           -------------------* m2
  1140.  *
  1141.  *    In this case p2 will be width/2 units from the segment m1-m2.
  1142.  *
  1143.  * Side effects:
  1144.  *    None.
  1145.  *
  1146.  *--------------------------------------------------------------
  1147.  */
  1148.  
  1149. void
  1150. TkGetButtPoints(p1, p2, width, project, m1, m2)
  1151.     double p1[];        /* Points to x- and y-coordinates of point
  1152.                  * before vertex. */
  1153.     double p2[];        /* Points to x- and y-coordinates of vertex
  1154.                  * for mitered joint. */
  1155.     double width;        /* Width of line.  */
  1156.     int project;        /* Non-zero means project p2 by an additional
  1157.                  * width/2 before computing m1 and m2. */
  1158.     double m1[];        /* Points to place to put "left" result
  1159.                  * point, as you face from p1 to p2. */
  1160.     double m2[];        /* Points to place to put "right" result
  1161.                  * point. */
  1162. {
  1163.     double length;        /* Length of p1-p2 segment. */
  1164.     double deltaX, deltaY;    /* Increments in coords. */
  1165.  
  1166.     width *= 0.5;
  1167.     length = hypot(p2[0] - p1[0], p2[1] - p1[1]);
  1168.     if (length == 0.0) {
  1169.     m1[0] = m2[0] = p2[0];
  1170.     m1[1] = m2[1] = p2[1];
  1171.     } else {
  1172.     deltaX = -width * (p2[1] - p1[1]) / length;
  1173.     deltaY = width * (p2[0] - p1[0]) / length;
  1174.     m1[0] = p2[0] + deltaX;
  1175.     m2[0] = p2[0] - deltaX;
  1176.     m1[1] = p2[1] + deltaY;
  1177.     m2[1] = p2[1] - deltaY;
  1178.     if (project) {
  1179.         m1[0] += deltaY;
  1180.         m2[0] += deltaY;
  1181.         m1[1] -= deltaX;
  1182.         m2[1] -= deltaX;
  1183.     }
  1184.     }
  1185. }
  1186.